/*
 * @Author: lichao 1246877006@qq.com
 * @Date: 2024-09-24 10:49:09
 * @LastEditors: lichao 1246877006@qq.com
 * @LastEditTime: 2024-09-24 17:09:46
 * @FilePath: \hello-algo\02迭代与递归\2.2.2递归.js
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE，
 */
/**
 * 递归是一种算法策略 通过调用自身来解决问题 主要包含两个阶段
 *  递：程序不断深入的调用自身，通常传入更小或者简化参数，知道达到终止条件
 *  归：触发终止条件后程序从最深层的递归函数开始逐层返回，汇聚每一层的结果
 * 而从实现的角度看，递归代码主要包含三个要素
 *  终止条件：用于决定什么时候有递转归
 *  递归调用：对应递，函数调用自身，通常输入更小或更简化的参数
 *  返回结果：对应归，将当前递归层级的结果返回至上一层
 */

// 递归 求和
function recursion(n) {
    if(n === 1) return 1
    const res = recursion(n - 1)
    return n + res
}

// 尾函数调用 js不支持
function tailRecursion(n, res) {
    if(n === 1) return 1
    return tailRecursion(n - 1, res + n)
}

// 递归树
function fib(n) {
    // 终止条件 f(1) = 1 f(0) = 0
    if(n === 1 || n === 0) return n - 1
    // 递归调用 f(n) = f(n - 1) + f(n - 2)
    const res = fib(n - 1) + fib(n - 2)
    return res
}

// 迭代模拟递归
function forLoopRecur(n) {
    const stack = []
    let res = 0
    for(let i = n; i > 0; i--) {
        stack.push(i)
    }
    while(stack.length) {
        res += stack.pop()
    }
    return res
}